package bag;

/**
 * 转化成 0-1 背包问题
 * 重点
 * 能否类的背包问题直接boolean[][] dp数组 boolean[i][j] 表示选i个能凑齐 j的可能性
 * 一样边界条件 状态转移方程
 */
public class 分割等和子集_416 {

    // 简化为1维dp数组 dp[j] 表示能否选到j
    public boolean canPartition_(int[] nums) {
        if (nums == null || nums.length == 0) return false;
        int sum = 0;
        int max = -1;
        for (int num : nums) {
            sum += num;
            max = Math.max(num, max);
        }
        int target = sum / 2;
        if (sum % 2 == 1) return false;

        if (max > target) return false;
        // dp[i][j] 表示前i个数  能不能选到子数组和为j
        // 因为第i个元素不选就等于 i-1   第i个元素选择就等于 i-1  j-nums[i]
        // 因而状态转移方程必须是二维的
        // 考虑一个数字都不选
        boolean dp[] = new boolean[target + 1];
        // 边界条件
        // 一个数字都不选   能使和为0
        dp[0] = true;
        // [1,5,11,5]  target 11
        // 首先我们考虑数组的含义：dp[i] 来表示取到和为 i 的方案是否存在。
        // 因为有nums.length个数，所以在外循环的层面我们要将 dp 这个数组下标从0到target更新nums.length遍（先不考虑边界的情况）
        // 然后考虑动态转移方程:对于目标为 j 的每个dp[j]，
        // 不选的状态是dp[j]（可以理解为维持上一轮，即在外层循环取前一个的数字时候的状态）；
        // 选的状态是dp[j-nums[i]]（理解为同目标是j-nums[i]的状态是一样的）
        // 两者只要有一种成立即可说明当前的状态是可行的,
        // （为什么要逆序，是因为dp后面的和的情况是从前面的情况转移过来的，
        // 如果前面的情况因为当前nums[i]的加入变为了True，比如dp[0 + nums[i]]变成了True，
        // 那么因为一个数只能用一次，dp[0 + nums[i] + nums[i]]不可以从dp[0 + nums[i]]转移过来。
        // 如果非要正序遍历，必须要多一个数组用于存储之前的情况。而逆序遍历可以省掉这个数组）

        for (int i = 1; i <= nums.length; i++) {
            for (int j = target; j > nums[i - 1]; j--) {
                //  0 -1 背包问题都是 反向更新  正向更新 前面的数字可能已经改了    跟直接用二维数组上一行的值有差别了
                // https://www.shangmayuan.com/a/032d88a05b554ecc82bfbfdf.html
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[target];
    }

    // 二维dp数组
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) return false;
        int sum = 0;
        int max = -1;
        for (int num : nums) {
            sum += num;
            max = Math.max(num, max);
        }
        int target = sum / 2;
        if (sum % 2 == 1) return false;

        if (max > target) return false;
        // dp[i][j] 表示前i个数  能不能选到子数组和为j
        // 因为第i个元素不选就等于 i-1   第i个元素选择就等于 i-1  j-nums[i]
        // 因而状态转移方程必须是二维的
        // 考虑一个数字都不选
        boolean dp[][] = new boolean[nums.length + 1][target + 1];
        // 边界条件
        // 一个数字都不选   能使和为0
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        // 一个数字都不选  肯定不能使和 >= 1
        for (int j = 1; j < target; j++) {
            dp[0][j] = false;
        }

        dp[1][nums[0]] = true;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                // dp公式   能不能达成条件 用 ||
                if (nums[i - 1] > j) {
                    // 只能不选nums[i]  才有可能凑齐j
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 不选nums[i] 或选 nums[i]  等于前一项能否组成子选项的可能性
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }

            }
        }
        return dp[nums.length][target];
    }
}
